package LeetCode;


import java.util.Stack;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}11:21
 */
public class M11 {

    public static void main(String[] args) {
        int[] test = {5,7,6,9,11,10,8};
        System.out.println(new M11().verifyPostorder(test));
    }


//    public boolean verifyPostorder(int[] postorder) {
//       return VerityPostorder(postorder,0,postorder.length-1);
//
//    }
//    public boolean VerityPostorder(int[] postorder,int start,int end){
//        if (start >= end){
//            return true;
//        }
//        int l = start;
//        while (postorder[l]<postorder[end]){
//            l++;
//        }
//        int m = l;
//        while (postorder[l]>postorder[end]){
//            l++;
//        }
//        return l==end&&VerityPostorder(postorder,start,m-1)&&VerityPostorder(postorder,m,end-1);//end-1因为要剔除根节点
//
//    }
    public boolean verifyPostorder(int[] postorder){
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length-1;i>=0;i--){
            if (postorder[i]>root){
                break;
            }
            while (!stack.isEmpty()&&stack.peek()>postorder[i]){
                root = stack.pop();
            }
            stack.add(postorder[i]);
        }
        return true;
    }
}
